C++链表

梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）

本教程将从链表的核心概念出发，详细讲解单链表、双向链表、循环链表的定义、实现及核心操作（初始化、插入、删除、遍历、查找），帮助你掌握C++中链表这一重要的数据结构。

教程目录导航

▼

一、链表核心概述

链表（Linked List）是一种非连续、非顺序的线性数据结构，由一系列节点（Node）组成，每个节点包含数据域（存储数据）和指针域（存储下一个/上一个节点的地址）。

与数组相比，链表的核心优势是：

动态扩容：无需预先分配固定内存，可根据需求动态添加节点；
高效插入/删除：无需移动大量元素，仅需修改指针指向；

核心劣势是：

随机访问效率低：无法直接通过下标访问，需从表头遍历；
额外空间开销：每个节点需存储指针域，占用更多内存。

链表的常见类型：单链表、双向链表、循环链表。

二、单链表

2.1 单链表概念

单链表是最简单的链表结构，每个节点仅包含数据域和后继指针域（指向直接后继节点），链表末尾节点的后继指针为nullptr（空指针），链表有一个头节点/头指针指向第一个有效节点。

单链表的特点：

只能从表头向表尾单向遍历；
查找、插入、删除操作均需从表头开始遍历；
实现简单，空间开销最小。

2.2 单链表的定义与实现

单链表的核心是节点结构体的定义，包含数据域和后继指针域：


#include <iostream>
#include <cstdlib>
using namespace std;

// 定义单链表节点结构体
struct ListNode {
    int data;               // 数据域：存储整型数据（可根据需求修改类型）
    ListNode* next;         // 指针域：指向后继节点
    
    // 构造函数：初始化节点
    ListNode(int val = 0) : data(val), next(nullptr) {}
};

// 定义单链表类（封装链表操作）
class SinglyLinkedList {
private:
    ListNode* head;         // 头指针：指向链表第一个节点
    int size;               // 链表节点个数
    
public:
    // 构造函数：初始化空链表
    SinglyLinkedList() : head(nullptr), size(0) {}
    
    // 析构函数：释放链表内存
    ~SinglyLinkedList() {
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* temp = curr;
            curr = curr->next;
            delete temp;
        }
        head = nullptr;
        size = 0;
    }

    // 声明核心操作函数（后续实现）
    void initList();                // 初始化链表
    void createList(int arr[], int n); // 从数组创建链表
    bool insertNode(int pos, int val); // 插入节点
    bool deleteNode(int pos);       // 删除节点
    ListNode* findNode(int val);    // 查找节点
    void traverseList();            // 遍历链表
    int getSize() { return size; }  // 获取链表长度
};

2.3 单链表的初始化与创建

2.3.1 初始化空链表

初始化链表，将头指针置空，节点数置0：


// 初始化空链表
void SinglyLinkedList::initList() {
    if (head != nullptr) { // 若链表非空，先释放内存
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* temp = curr;
            curr = curr->next;
            delete temp;
        }
    }
    head = nullptr;
    size = 0;
    cout << "链表初始化完成！" << endl;
}

2.3.2 从数组创建链表（尾插法）

尾插法：新节点始终插入到链表末尾，保持数据顺序与数组一致：


// 从数组创建链表（尾插法）
void SinglyLinkedList::createList(int arr[], int n) {
    initList(); // 先初始化空链表
    if (n <= 0) return;
    
    // 创建头节点
    head = new ListNode(arr[0]);
    ListNode* tail = head; // 尾指针，指向当前最后一个节点
    size = 1;
    
    // 遍历数组，逐个插入节点
    for (int i = 1; i < n; i++) {
        ListNode* newNode = new ListNode(arr[i]);
        tail->next = newNode; // 尾节点指向新节点
        tail = newNode;       // 尾指针后移
        size++;
    }
    cout << "链表创建完成，共" << size << "个节点！" << endl;
}

2.4 单链表的插入操作

插入规则：

插入位置范围：1 ~ size+1（1表示表头，size+1表示表尾）；
步骤：1. 找到插入位置的前驱节点；2. 新建节点；3. 修改指针指向。


// 插入节点：在第pos个位置插入值为val的节点（pos从1开始）
bool SinglyLinkedList::insertNode(int pos, int val) {
    // 检查位置合法性
    if (pos < 1 || pos > size + 1) {
        cout << "插入位置非法！" << endl;
        return false;
    }
    
    // 新建节点
    ListNode* newNode = new ListNode(val);
    
    // 情况1：插入到表头（pos=1）
    if (pos == 1) {
        newNode->next = head;
        head = newNode;
    }
    // 情况2：插入到表中/表尾
    else {
        ListNode* prev = head;
        // 找到第pos-1个节点（前驱节点）
        for (int i = 1; i < pos - 1; i++) {
            prev = prev->next;
        }
        newNode->next = prev->next;
        prev->next = newNode;
    }
    
    size++;
    cout << "节点" << val << "插入到位置" << pos << "成功！" << endl;
    return true;
}

2.5 单链表的删除操作

删除规则：

删除位置范围：1 ~ size；
步骤：1. 找到待删除节点的前驱节点；2. 修改指针指向；3. 释放待删除节点内存。


// 删除第pos个位置的节点（pos从1开始）
bool SinglyLinkedList::deleteNode(int pos) {
    // 检查位置合法性
    if (pos < 1 || pos > size) {
        cout << "删除位置非法！" << endl;
        return false;
    }
    
    ListNode* delNode = nullptr;
    
    // 情况1：删除表头节点（pos=1）
    if (pos == 1) {
        delNode = head;
        head = head->next;
    }
    // 情况2：删除表中/表尾节点
    else {
        ListNode* prev = head;
        // 找到第pos-1个节点（前驱节点）
        for (int i = 1; i < pos - 1; i++) {
            prev = prev->next;
        }
        delNode = prev->next;
        prev->next = delNode->next;
    }
    
    // 释放删除节点的内存
    int delVal = delNode->data;
    delete delNode;
    delNode = nullptr;
    size--;
    
    cout << "位置" << pos << "的节点" << delVal << "删除成功！" << endl;
    return true;
}

2.6 单链表的遍历与查找

2.6.1 遍历链表

从表头开始，逐个访问节点数据，直到链表末尾：


// 遍历链表并输出所有节点数据
void SinglyLinkedList::traverseList() {
    if (head == nullptr) {
        cout << "链表为空！" << endl;
        return;
    }
    
    cout << "链表节点：";
    ListNode* curr = head;
    while (curr != nullptr) {
        cout << curr->data << " ";
        curr = curr->next;
    }
    cout << endl;
}

2.6.2 查找节点

按值查找，返回第一个匹配值的节点指针（未找到返回nullptr）：


// 查找值为val的节点，返回节点指针（未找到返回nullptr）
ListNode* SinglyLinkedList::findNode(int val) {
    ListNode* curr = head;
    while (curr != nullptr) {
        if (curr->data == val) {
            cout << "找到节点" << val << "！" << endl;
            return curr;
        }
        curr = curr->next;
    }
    cout << "未找到节点" << val << "！" << endl;
    return nullptr;
}

单链表测试示例


// 测试单链表
int main() {
    SinglyLinkedList list;
    
    // 创建链表
    int arr[] = {10, 20, 30, 40, 50};
    list.createList(arr, 5);
    list.traverseList(); // 输出：10 20 30 40 50
    
    // 插入节点
    list.insertNode(3, 25);
    list.traverseList(); // 输出：10 20 25 30 40 50
    
    // 删除节点
    list.deleteNode(5);
    list.traverseList(); // 输出：10 20 25 30 50
    
    // 查找节点
    list.findNode(25);   // 找到节点25
    list.findNode(60);   // 未找到节点60
    
    cout << "链表长度：" << list.getSize() << endl; // 输出：5
    
    return 0;
}

三、双向链表

3.1 双向链表概念

双向链表（Doubly Linked List）每个节点包含数据域、前驱指针域（指向前驱节点）和后继指针域（指向后继节点）。表头节点的前驱指针为nullptr，表尾节点的后继指针为nullptr。

双向链表的特点：

可双向遍历（从表头到表尾/从表尾到表头）；
插入/删除操作需同时修改前驱和后继指针；
空间开销比单链表大，但操作更灵活。

3.2 双向链表的定义与实现


#include <iostream>
#include <cstdlib>
using namespace std;

// 定义双向链表节点结构体
struct DListNode {
    int data;               // 数据域
    DListNode* prev;        // 前驱指针：指向前一个节点
    DListNode* next;        // 后继指针：指向后一个节点
    
    // 构造函数
    DListNode(int val = 0) : data(val), prev(nullptr), next(nullptr) {}
};

// 定义双向链表类
class DoublyLinkedList {
private:
    DListNode* head;        // 头指针
    DListNode* tail;        // 尾指针（优化尾插/尾删效率）
    int size;               // 节点个数
    
public:
    // 构造函数
    DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}
    
    // 析构函数
    ~DoublyLinkedList() {
        DListNode* curr = head;
        while (curr != nullptr) {
            DListNode* temp = curr;
            curr = curr->next;
            delete temp;
        }
        head = tail = nullptr;
        size = 0;
    }

    // 声明核心操作函数
    void initList();                // 初始化
    void createList(int arr[], int n); // 创建链表
    bool insertNode(int pos, int val); // 插入
    bool deleteNode(int pos);       // 删除
    DListNode* findNode(int val);   // 查找
    void traverseForward();         // 正向遍历
    void traverseBackward();        // 反向遍历
    int getSize() { return size; }
};

3.3 双向链表的初始化与创建

3.3.1 初始化空链表


// 初始化空链表
void DoublyLinkedList::initList() {
    if (head != nullptr) {
        DListNode* curr = head;
        while (curr != nullptr) {
            DListNode* temp = curr;
            curr = curr->next;
            delete temp;
        }
    }
    head = tail = nullptr;
    size = 0;
    cout << "双向链表初始化完成！" << endl;
}

3.3.2 从数组创建链表（尾插法）


// 从数组创建双向链表（尾插法）
void DoublyLinkedList::createList(int arr[], int n) {
    initList();
    if (n <= 0) return;
    
    // 创建第一个节点
    head = new DListNode(arr[0]);
    tail = head;
    size = 1;
    
    // 逐个插入后续节点
    for (int i = 1; i < n; i++) {
        DListNode* newNode = new DListNode(arr[i]);
        tail->next = newNode;    // 尾节点后继指向新节点
        newNode->prev = tail;    // 新节点前驱指向尾节点
        tail = newNode;          // 尾指针后移
        size++;
    }
    cout << "双向链表创建完成，共" << size << "个节点！" << endl;
}

3.4 双向链表的插入操作


// 在第pos个位置插入值为val的节点（pos从1开始）
bool DoublyLinkedList::insertNode(int pos, int val) {
    if (pos < 1 || pos > size + 1) {
        cout << "插入位置非法！" << endl;
        return false;
    }
    
    DListNode* newNode = new DListNode(val);
    
    // 情况1：插入到表头
    if (pos == 1) {
        if (head == nullptr) { // 空链表
            head = tail = newNode;
        } else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
    }
    // 情况2：插入到表尾
    else if (pos == size + 1) {
        tail->next = newNode;
        newNode->prev = tail;
        tail = newNode;
    }
    // 情况3：插入到表中
    else {
        DListNode* curr = head;
        // 找到第pos个节点
        for (int i = 1; i < pos; i++) {
            curr = curr->next;
        }
        // 修改指针
        newNode->prev = curr->prev;
        newNode->next = curr;
        curr->prev->next = newNode;
        curr->prev = newNode;
    }
    
    size++;
    cout << "节点" << val << "插入到位置" << pos << "成功！" << endl;
    return true;
}

3.5 双向链表的删除操作


// 删除第pos个位置的节点（pos从1开始）
bool DoublyLinkedList::deleteNode(int pos) {
    if (pos < 1 || pos > size) {
        cout << "删除位置非法！" << endl;
        return false;
    }
    
    DListNode* delNode = nullptr;
    
    // 情况1：删除表头节点
    if (pos == 1) {
        delNode = head;
        head = head->next;
        if (head != nullptr) {
            head->prev = nullptr;
        } else { // 链表只剩一个节点
            tail = nullptr;
        }
    }
    // 情况2：删除表尾节点
    else if (pos == size) {
        delNode = tail;
        tail = tail->prev;
        tail->next = nullptr;
    }
    // 情况3：删除表中节点
    else {
        delNode = head;
        for (int i = 1; i < pos; i++) {
            delNode = delNode->next;
        }
        delNode->prev->next = delNode->next;
        delNode->next->prev = delNode->prev;
    }
    
    // 释放内存
    int delVal = delNode->data;
    delete delNode;
    delNode = nullptr;
    size--;
    
    cout << "位置" << pos << "的节点" << delVal << "删除成功！" << endl;
    return true;
}

3.6 双向链表的遍历与查找

3.6.1 正向遍历（表头→表尾）


// 正向遍历（表头到表尾）
void DoublyLinkedList::traverseForward() {
    if (head == nullptr) {
        cout << "双向链表为空！" << endl;
        return;
    }
    
    cout << "正向遍历：";
    DListNode* curr = head;
    while (curr != nullptr) {
        cout << curr->data << " ";
        curr = curr->next;
    }
    cout << endl;
}

3.6.2 反向遍历（表尾→表头）


// 反向遍历（表尾到表头）
void DoublyLinkedList::traverseBackward() {
    if (tail == nullptr) {
        cout << "双向链表为空！" << endl;
        return;
    }
    
    cout << "反向遍历：";
    DListNode* curr = tail;
    while (curr != nullptr) {
        cout << curr->data << " ";
        curr = curr->prev;
    }
    cout << endl;
}

3.6.3 查找节点


// 查找值为val的节点（正向查找）
DListNode* DoublyLinkedList::findNode(int val) {
    DListNode* curr = head;
    while (curr != nullptr) {
        if (curr->data == val) {
            cout << "找到节点" << val << "！" << endl;
            return curr;
        }
        curr = curr->next;
    }
    cout << "未找到节点" << val << "！" << endl;
    return nullptr;
}

双向链表测试示例


// 测试双向链表
int main() {
    DoublyLinkedList dlist;
    
    // 创建链表
    int arr[] = {1, 2, 3, 4, 5};
    dlist.createList(arr, 5);
    dlist.traverseForward();  // 输出：1 2 3 4 5
    dlist.traverseBackward(); // 输出：5 4 3 2 1
    
    // 插入节点
    dlist.insertNode(3, 8);
    dlist.traverseForward();  // 输出：1 2 8 3 4 5
    
    // 删除节点
    dlist.deleteNode(4);
    dlist.traverseForward();  // 输出：1 2 8 4 5
    
    // 查找节点
    dlist.findNode(8);        // 找到节点8
    dlist.findNode(9);        // 未找到节点9
    
    cout << "链表长度：" << dlist.getSize() << endl; // 输出：5
    
    return 0;
}

四、循环链表

4.1 循环链表概念

循环链表是单链表的变种，表尾节点的后继指针不指向nullptr，而是指向表头节点（单循环链表）或头节点（带哨兵头节点的循环链表），形成闭合的环。

循环链表的特点：

可从任意节点开始遍历整个链表；
无需额外指针即可找到表尾（表尾节点的后继为表头）；
常用作队列、环形缓冲区等场景。

本教程以单循环链表为例讲解。

4.2 循环链表的定义与实现


#include <iostream>
#include <cstdlib>
using namespace std;

// 定义循环链表节点结构体
struct CListNode {
    int data;               // 数据域
    CListNode* next;        // 后继指针
    
    // 构造函数
    CListNode(int val = 0) : data(val), next(nullptr) {}
};

// 定义循环链表类
class CircularLinkedList {
private:
    CListNode* head;        // 头指针
    int size;               // 节点个数
    
public:
    // 构造函数
    CircularLinkedList() : head(nullptr), size(0) {}
    
    // 析构函数
    ~CircularLinkedList() {
        if (head == nullptr) return;
        
        CListNode* curr = head->next;
        // 遍历并释放所有节点
        while (curr != head) {
            CListNode* temp = curr;
            curr = curr->next;
            delete temp;
        }
        delete head;
        head = nullptr;
        size = 0;
    }

    // 声明核心操作函数
    void initList();                // 初始化
    void createList(int arr[], int n); // 创建链表
    bool insertNode(int pos, int val); // 插入
    bool deleteNode(int pos);       // 删除
    CListNode* findNode(int val);   // 查找
    void traverseList();            // 遍历
    int getSize() { return size; }
};

4.3 循环链表的初始化与创建

4.3.1 初始化空链表


// 初始化空链表
void CircularLinkedList::initList() {
    if (head != nullptr) {
        // 释放循环链表所有节点
        CListNode* curr = head->next;
        while (curr != head) {
            CListNode* temp = curr;
            curr = curr->next;
            delete temp;
        }
        delete head;
    }
    head = nullptr;
    size = 0;
    cout << "循环链表初始化完成！" << endl;
}

4.3.2 从数组创建链表（尾插法）


// 从数组创建循环链表（尾插法）
void CircularLinkedList::createList(int arr[], int n) {
    initList();
    if (n <= 0) return;
    
    // 创建第一个节点
    head = new CListNode(arr[0]);
    CListNode* tail = head;
    size = 1;
    
    // 插入后续节点
    for (int i = 1; i < n; i++) {
        CListNode* newNode = new CListNode(arr[i]);
        tail->next = newNode;
        tail = newNode;
        size++;
    }
    // 尾节点指向头节点，形成循环
    tail->next = head;
    
    cout << "循环链表创建完成，共" << size << "个节点！" << endl;
}

4.4 循环链表的插入操作


// 在第pos个位置插入值为val的节点（pos从1开始）
bool CircularLinkedList::insertNode(int pos, int val) {
    if (pos < 1 || pos > size + 1) {
        cout << "插入位置非法！" << endl;
        return false;
    }
    
    CListNode* newNode = new CListNode(val);
    
    // 情况1：空链表插入第一个节点
    if (head == nullptr) {
        head = newNode;
        newNode->next = head;
    }
    // 情况2：插入到表头（pos=1）
    else if (pos == 1) {
        // 找到尾节点
        CListNode* tail = head;
        while (tail->next != head) {
            tail = tail->next;
        }
        newNode->next = head;
        tail->next = newNode;
        head = newNode; // 头指针指向新节点
    }
    // 情况3：插入到表中/表尾
    else {
        CListNode* prev = head;
        // 找到第pos-1个节点
        for (int i = 1; i < pos - 1; i++) {
            prev = prev->next;
        }
        newNode->next = prev->next;
        prev->next = newNode;
        
        // 若插入到表尾，更新尾节点（可选，本实现未维护尾指针）
        if (pos == size + 1) {
            newNode->next = head;
        }
    }
    
    size++;
    cout << "节点" << val << "插入到位置" << pos << "成功！" << endl;
    return true;
}

4.5 循环链表的删除操作


// 删除第pos个位置的节点（pos从1开始）
bool CircularLinkedList::deleteNode(int pos) {
    if (pos < 1 || pos > size) {
        cout << "删除位置非法！" << endl;
        return false;
    }
    
    CListNode* delNode = nullptr;
    CListNode* tail = nullptr;
    
    // 情况1：链表只有一个节点
    if (size == 1) {
        delNode = head;
        head = nullptr;
    }
    // 情况2：删除表头节点
    else if (pos == 1) {
        // 找到尾节点
        tail = head;
        while (tail->next != head) {
            tail = tail->next;
        }
        delNode = head;
        head = head->next;
        tail->next = head; // 尾节点指向新表头
    }
    // 情况3：删除表中/表尾节点
    else {
        CListNode* prev = head;
        // 找到第pos-1个节点
        for (int i = 1; i < pos - 1; i++) {
            prev = prev->next;
        }
        delNode = prev->next;
        prev->next = delNode->next;
        
        // 若删除表尾节点，确保尾节点指向表头
        if (delNode->next == head && pos == size) {
            prev->next = head;
        }
    }
    
    // 释放内存
    int delVal = delNode->data;
    delete delNode;
    delNode = nullptr;
    size--;
    
    cout << "位置" << pos << "的节点" << delVal << "删除成功！" << endl;
    return true;
}

4.6 循环链表的遍历与查找

4.6.1 遍历链表

遍历循环链表需注意终止条件（回到头节点），避免无限循环：


// 遍历循环链表
void CircularLinkedList::traverseList() {
    if (head == nullptr) {
        cout << "循环链表为空！" << endl;
        return;
    }
    
    cout << "循环链表节点：";
    CListNode* curr = head;
    do {
        cout << curr->data << " ";
        curr = curr->next;
    } while (curr != head); // 终止条件：回到头节点
    cout << endl;
}

4.6.2 查找节点


// 查找值为val的节点
CListNode* CircularLinkedList::findNode(int val) {
    if (head == nullptr) {
        cout << "循环链表为空！" << endl;
        return nullptr;
    }
    
    CListNode* curr = head;
    do {
        if (curr->data == val) {
            cout << "找到节点" << val << "！" << endl;
            return curr;
        }
        curr = curr->next;
    } while (curr != head);
    
    cout << "未找到节点" << val << "！" << endl;
    return nullptr;
}

循环链表测试示例


// 测试循环链表
int main() {
    CircularLinkedList clist;
    
    // 创建链表
    int arr[] = {100, 200, 300, 400, 500};
    clist.createList(arr, 5);
    clist.traverseList(); // 输出：100 200 300 400 500
    
    // 插入节点
    clist.insertNode(2, 150);
    clist.traverseList(); // 输出：100 150 200 300 400 500
    
    // 删除节点
    clist.deleteNode(5);
    clist.traverseList(); // 输出：100 150 200 300 500
    
    // 查找节点
    clist.findNode(300);   // 找到节点300
    clist.findNode(600);   // 未找到节点600
    
    cout << "链表长度：" << clist.getSize() << endl; // 输出：5
    
    return 0;
}

五、注意事项

内存管理：链表节点均在堆区分配，必须在析构函数/删除操作中释放内存，避免内存泄漏；
空指针检查：操作链表前需检查头指针/节点指针是否为nullptr，避免程序崩溃；
循环链表终止条件：遍历/查找循环链表时，终止条件为“回到头节点”，而非nullptr；
双向链表指针修改：插入/删除时需同时修改前驱和后继指针，顺序错误会导致链表断裂；
位置合法性：插入/删除操作前必须检查位置是否在合法范围（1 ~ size+1 插入，1 ~ size 删除）；
头/尾指针维护：双向链表/循环链表建议维护尾指针，可大幅提升尾插/尾删效率；
避免野指针：释放节点后需将指针置为nullptr，避免野指针访问。

六、总结

链表是动态线性数据结构，核心由节点组成，通过指针连接，无需连续内存，插入/删除效率高但随机访问效率低；
单链表：单向遍历，实现简单，空间开销最小，适用于简单的顺序访问场景；
双向链表：双向遍历，插入/删除需修改两个指针，空间开销大但操作灵活，适用于需频繁前后遍历的场景；
循环链表：首尾相连，可从任意节点遍历全表，适用于环形缓冲区、队列等场景；
链表操作的核心是指针的修改，需注意内存释放、空指针检查、终止条件等细节，避免链表断裂或内存泄漏。

掌握链表的实现与操作，是理解更复杂数据结构（如链表版栈、队列、哈希表）的基础，也是C++数据结构学习的核心内容之一。

返回顶部